# 方法一 O（n）
class Solution:
    def trailingZeroes(self, n: int) -> int:
        if n == 0:
            return 0
        def factorial(n):
            if n == 1:
                return 1
            else:
                return n * factorial(n - 1)
        ans = factorial(n)
        ret = 0
        while ans >= 10:
            remainder = ans % 10
            ans = ans // 10
            if remainder == 0:
                ret += 1
            else:
                return ret
        return ret
# 方法二 O（n） 但不用递归求阶乘值
class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        for i in range(5, n + 1, 5):
            while i % 5 == 0:
                i //= 5
                ans += 1
        return ans
# 方法三 O(lon（n）)
class Solution:
    def trailingZeroes(self, n: int) -> int:
        ans = 0
        while n:
            n //= 5
            ans += n
        return ans